package com.yun.algorithmproblem.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.stream.Collectors;

public class Leetcode1206_SkipList {
    public static void main(String[] args) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < 1000; i++) {
            int level = randomLevel(5);
            map.compute(level, (k, v) -> v == null ? 1 : v + 1);
        }
        System.out.println(map.entrySet().stream().collect(
                Collectors.toMap(
                        Map.Entry::getKey,
                        e -> String.format("%d%%", e.getValue() * 100 / 1000)
                )
        ));
    }

    /*
        设计一个方法,方法会随机返回1~max的数字
        从1开始,数字的几率逐级减半,例如max=4,让大概
            -50%的几率返回1
            -25%的几率返回2
            -12.5%的几率返回3
            -12.5%的几率返回4
     */
    static Random r = new Random();

    static int randomLevel(int max) {
        int x = 1;
        while (x < max) {
            if (r.nextBoolean()) {
                return x;
            }
            x++;
        }
        return x;
    }

    static class SkipList {
        private static final int MAX = 10;//redis 32 java 62
        private final Node head = new Node(-1);

        static class Node {
            int val;//值
            Node[] next = new Node[MAX];//next数组

            public Node(int val) {
                this.val = val;
            }
        }

        public Node[] find(int val) {
            Node[] path = new Node[MAX];
            Node curr = head;
            for (int level = MAX - 1; level >= 0; level--) {//从上向下找
                while (curr.next[level] != null && curr.next[level].val < val) {
                    curr = curr.next[level];
                }
                path[level] = curr;
            }
            return path;
        }

        public boolean search(int val) {
            Node[] path = find(val);
            Node node = path[0].next[0];
            return node != null && node.val == val;
        }

        public void add(int val) {
            //1.确定添加位置(把val当作目标查询,经历的路径就可以确定添加位置
            Node[] path = find(val);
            //2.创建新节点随机高度
            Node node = new Node(val);
            int level = randomLevel(MAX);
            //3.修改路径节点next指针,以及新节点next指针
            for (int i = 0; i < level; i++) {
                node.next[i] = path[i].next[i];
                path[i].next[i] = node;
            }
        }

        public boolean erase(int val) {
            Node[] path = find(val);
            Node node = path[0].next[0];
            if (node == null || node.val != val) {
                return false;
            }
            for (int i = 0; i < MAX; i++) {
                if (path[i].next[i] != node) {
                    break;
                }
                path[i].next[i] = node.next[i];
            }
            return true;
        }
    }
}
